<?php
/**
 * @title 309. 最佳买卖股票时机含冷冻期 - 递归
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        /**
         * @since 2020-07-25 dps缓存
         */
        $this->dps = [];

        /**
         * @since 2020-07-25 增加一个数组长度, 避免对数组反复切割
         */
        $n = count($prices);
        return self::dp($prices, $n);
    }

    /**
     * @title 递归
     * @author start2004
     * @since 2020-07-10 Created
     *
     * @param array $prices
     * @param int $n
     * @return int|mixed
     */
    function dp($prices = [], $n = 0){
        if(isset($this->dps[$n])){
            return $this->dps[$n];
        } else {}

        /**
         * @since 2020-07-25 极端情况处理
         */
        if($n<=1){
            $result = 0;
        } elseif($n==2) {
            $result = max(0, $prices[1]-$prices[0]);
        } else {
            /**
             * @since 2020-07-10 第n天不进行任何操作, 就是 `dp(n-1)`
             */
            $result = self::dp($prices, $n-1);

            /**
             * @since 2020-07-10 递归第n天是`卖`操作, 对应操作的买应是第1天到第n-1天
             * @since 2020-08-06 第4天买, 第n天卖, 扣去1天冷冻期, 前2天还可以进行股票操作, 即dp(2)
             */
            for ($i=0; $i<=$n-2; $i++){
                $result = max($result, $prices[$n-1]-$prices[$i] + self::dp($prices, $i-1));
            }
        }

        /**
         * @return
         */
        $this->dps[$n] = $result;
        return $result;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.10.php
 */
$datas = [
    [1,2,3,0,2],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->maxProfit($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
